package com.samxcode.leetcode;

/**
 * Given an array S of n integers, find three integers in S such that the sum is closest to a given
 * number, target. Return the sum of the three integers. You may assume that each input would have
 * exactly one solution.
 * 
 * Solution:
 * similar to the solution of ThreeSum, just make a variable to update the closest number
 * 
 * @author Sam
 *
 */
public class ThreeSumCloset {

    public static void main(String[] args) {
        int[] num = { 1, 2, 4, 8, 16, 32, 64, 128 };
        threeSumClosest(num, 82);
    }


    public static int threeSumClosest(int[] num, int target) {
        Sort.insertSort(num);
        int font, back;
        int diff = Integer.MAX_VALUE, sum = 0;
        boolean flag = true;
        for (int i = 0; i < num.length - 2 && flag; i++) {
            // skip i when this number is same to the previous
            if (i > 0 && num[i] == num[i - 1]) {
                continue;
            }
            font = i + 1;
            back = num.length - 1;
            while (font < back) {
                int tempSum = num[i] + num[font] + num[back];
                int tempDiff = Math.abs(tempSum - target);
                if (tempDiff < diff) {
                    diff = tempDiff;
                    sum = tempSum;
                }
                if (tempSum < target) {
                    // update font and remove duplicates
                    do {
                        font++;
                    } while (font < back && num[font] == num[font - 1]);
                } else if (tempSum > target) {
                    // update back and remove duplicates
                    do {
                        back--;
                    } while (back > font && num[back] == num[back + 1]);
                } else {
                    // if the sum is equal to the target, then exit the loop
                    flag = false;
                    break;
                }
            }
        }
        return sum;
    }
}
